/*********************************************************
          File Name:9.52.h
          Author: Abby Cin
          Mail: abbytsing@gmail.com
          Created Time: Tue 09 Feb 2016 09:06:48 PM CST
**********************************************************/

#ifndef CH09_52_H
#define CH09_52_H

#include <stdexcept>

#ifdef __x86_64 
typedef unsigned long size_t;
#else
typedef unsigned int size_t;
#endif

namespace nm
{
    template<typename T>
    class list final
    {
        private:
            struct node
            {
                T elem;
                node *nxt;
            };
            node *head, *tmp_node;
            size_t len;
        public:
            list()
            {
                head = new node;
                head->nxt = nullptr;
                tmp_node = nullptr;
                len = 0;
            }
            ~list()
            {
                node *cur, *tmp;
                cur = head->nxt;
                while(cur)
                {
                    tmp = cur->nxt;
                    delete cur;
                    cur = tmp;
                }
                delete head;
            }
            void push_back(T &x)
            {
                node *tmp = new node;
                tmp_node = head;
                tmp->elem = x;
                while(tmp_node->nxt)
                    tmp_node = tmp_node->nxt;
                tmp->nxt = nullptr;
                tmp_node->nxt = tmp;
                len += 1;
            }

            void pop_back()
            {
                if(len == 0)
                    return;
                node *tmp = head;
                while(tmp->nxt)
                {
                    tmp_node = tmp;
                    tmp = tmp->nxt;
                }
                delete tmp; 
                tmp_node->nxt = nullptr;
                len -= 1;
            }

            size_t size() const
            {
                return len;
            }

            bool empty() const
            {
                return (len == 0);
            }

            T &operator[] (size_t x) const 
            {
                if(empty())
                    throw std::runtime_error("stack is emptry!");
                if(x >= len)
                    throw std::out_of_range("index out of range!");
                node *tmp = head->nxt;;
                while(x--)
                {
                    tmp = tmp->nxt;
                }
                return tmp->elem;
            }
    };

    template<typename T, typename M=nm::list<T>>
    class stack final
    {
        public:
            stack(){}
            ~stack(){}
            T top() const
            {
                return mem[mem.size() - 1];
            }
            void pop()
            {
                mem.pop_back();
            }
            void push(T &x)
            {
                mem.push_back(x);
            }
            bool empty() const
            {
                return mem.empty();
            }
            size_t size()
            {
                return mem.size();
            }
        private:
            M mem;   
    };
}
#endif
